1. Field of the Invention
The present invention relates to the design of computer systems that support automatic memory management for objects defined within an object-oriented programming system. More specifically, the present invention relates to a method and an apparatus for skewing a bi-directional object layout to provide good cache behavior, wherein the bi-directional object layout allows reference fields within an object to be easily identified for garbage collection purposes.
2. Related Art
Programming languages with automatic memory management, such as the JAVA™ programming language, are widely recognized for making software easier to develop. Unlike conventional programming languages, such as C or C++, that require programmers to perform explicit memory deallocation operations to manage dynamic data structures, the JAVA programming language takes care of memory management automatically.
Automatic memory management systems typically allocate objects from memory as they are needed during execution of a program. When objects are no longer being used by the program, they are typically reclaimed through a process known as “garbage collection.”
Garbage collection typically operates by first identifying and marking “live” objects that are reachable from roots of a program. Once all reachable objects are marked, all remaining objects that are not marked are considered “garbage.” These remaining objects are subsequently reclaimed to make room in memory.
During the marking process, it is advantageous to be able to rapidly determine which fields within an object are “reference fields” that can potentially point to other reachable objects. One way to accomplish this is to use a bi-directional object layout, which allows a reference field to be identified by examining its offset.
Referring to FIG. 1, a conventional object layout 102 includes a header 106 that is located at offset zero from a base address 104 for the object. Object layout 102 also includes other fields at increasing offsets, including scalar fields 108 and reference fields 110. (Note that scalar fields 108 and reference fields 110 can be intermixed.) Each subclass appends fields in order.
In contrast, a bi-directional object layout 112 uses negative offsets for reference fields. This bi-directional layout 112 grows in both directions from the header 116. Scalar fields are placed at positive offsets and reference fields are placed at negative offsets. This allows a reference field to be identified immediately by examining its offset. This bi-directional object layout scheme is described in more detail in U.S. Pat. No. 5,900,001, entitled “Method and Apparatus for Optimizing Exact Garbage Collection Using a Bifurcated Data Structure,” by inventors Mario I. Wolczko and David M. Ungar, issued May 4, 1999.
Although use of a bi-directional layout can greatly improve system performance during garbage collection, it often has the unfortunate side-effect of causing small objects to occupy two cache lines in a cache that is part of an object-based memory hierarchy because of the way offsets are aligned with the base address of a cache line. For example, assuming a 64-byte cache line and 4-byte references, an object header (at offset zero) is the first word in one cache line, and a class reference at, for example, offset −4 is the final word in a preceding cache line starting at offset −64. Splitting small objects across two cache lines in this way leads to unused cache space and unnecessary data transfers.
What is needed is a method and apparatus that facilitates using a bi-directional object layout without the above-described problems.